import java.util.LinkedList;
public class SolutionZsh {

public int orangesRotting(int[][] grid) {

        LinkedList<Integer> oldBad = new LinkedList<>();
        LinkedList<Integer> newBad = new LinkedList<>();
        int goodGridCount = 0;
        int time = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) goodGridCount++;
                if (grid[i][j] == 2) oldBad.add(i << 4 | j);
            }
        }

        if (goodGridCount == 0) return 0;

        while (goodGridCount != 0  && !(oldBad.isEmpty() && newBad.isEmpty())) {
            goodGridCount -= infection(oldBad, newBad, grid);
            // 更换队列
            LinkedList<Integer> temp = oldBad;
            oldBad = newBad;
            newBad = temp;
            time++;
        }

        return goodGridCount == 0 ? time : -1;
    }

    public int infection(LinkedList<Integer> oldBad, LinkedList<Integer> newBad, int[][] grid) {

        int infectionCount = 0;
        while (!oldBad.isEmpty()) {
            Integer index = oldBad.poll();
            int x = index >> 4;
            int y = index & 0x0F;
            // 判断并感染
            infectionCount += doInfection(x - 1, y, grid, newBad) +  // 验证上边
                    doInfection(x + 1, y, grid, newBad) + // 验证下边
                    doInfection(x, y - 1, grid, newBad) + // 验证左边
                    doInfection(x, y + 1, grid, newBad); // 验证右边

        }
        return infectionCount;
    }

    public int doInfection(int x, int y, int[][] grid, LinkedList<Integer> newBad) {

        if (x >= 0 && x < grid.length && y >= 0 && y < grid[0].length && grid[x][y] == 1) {
            grid[x][y] = 2;
            newBad.add(x << 4 | y);
            return 1;
        }
        return 0;
    }
}